#include <iostream>
#include <stdio.h>
using namespace std;

struct ListNode 
{
    int val;
    struct ListNode *next;
    ListNode(int x) :val(x), next(NULL)
    { }
};
class Solution 
{
public:
    static ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
        ListNode *newhead=NULL;
        ListNode *newtail=NULL;

        ListNode *head1=pHead1;
        ListNode *head2=pHead2;
        while(head1!=NULL && head2!=NULL)
        {
            if(head1->val<head2->val)
            {
                if(newhead==NULL)
                {
                    ListNode *tmp=new ListNode (head1->val);
                    newhead=newtail=tmp;
                }
                else
                {
                    newtail->next=new ListNode (head1->val);
                    newtail=newtail->next;
                }
                head1=head1->next;
            }
            else
            {
                if(newhead==NULL)
                {
                    newhead=newtail=new ListNode(head2->val);
                }
                else
                {
                    newtail->next=new ListNode(head2->val);
                    newtail=newtail->next;
                }
                head2=head2->next;
            }
        }
        while(head1!=NULL)
        {
            if(newhead==NULL)
            {
                newhead=newtail=new ListNode(head1->val);
            }
            else
            {
                newtail->next=new ListNode(head1->val);
                newtail=newtail->next;
            }
            head1=head1->next;
        }
        while(head2!=NULL)
        {
            if(newhead==NULL)
            {
                newhead=newtail=new ListNode(head2->val);
            }
            else
            {
                newtail->next=new ListNode(head2->val);
                newtail=newtail->next;
            }
            head2=head2->next;
        }
        return newhead;
    }
};
void test()
{
    ListNode *pos_2=new ListNode(2);
    ListNode *pos_4=new ListNode(4);
    ListNode *pos_6=new ListNode(6);
    ListNode *pos_8=new ListNode(8);
    pos_2->next=pos_4;
    pos_4->next=pos_6;
    pos_6->next=pos_8;
    ListNode *pos_1=new ListNode(1);
    ListNode *pos_3=new ListNode(3);
    ListNode *pos_5=new ListNode(5);
    ListNode *pos_7=new ListNode(7);
    pos_1->next=pos_3;
    pos_3->next=pos_5;
    pos_5->next=pos_7;

    ListNode * ret=Solution::Merge(pos_1,pos_2);
    while(ret!=NULL)
    {
        printf("%d ",ret->val);
        ret=ret->next;
    }
}

int main()
{
    test();
    return 0;
}
